import java.io.*;

// 现在有一个打怪类型的游戏，这个游戏是这样的，你有n个技能
// 每一个技能会有一个伤害，
// 同时若怪物小于等于一定的血量，则该技能可能造成双倍伤害
// 每一个技能最多只能释放一次，已知怪物有m点血量
// 现在想问你最少用几个技能能消灭掉他(血量小于等于0)
// 技能的数量是n，怪物的血量是m
// i号技能的伤害是x[i]，i号技能触发双倍伤害的血量最小值是y[i]
// 1 <= n <= 10
// 1 <= m、x[i]、y[i] <= 10^6
// 测试链接 : https://www.nowcoder.com/practice/d88ef50f8dab4850be8cd4b95514bbbd
public class KillMonsterEverySkillUseOnce {
    public static int MAX = 11;

    public static int[] kill = new int[MAX];

    public static int[] blood = new int[MAX];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        while(in.nextToken() != StreamTokenizer.TT_EOF){
            int t = (int) in.nval;
            for(int i = 0; i < t ; i++){
                in.nextToken();
                int n = (int) in.nval;  //代表有n个技能
                in.nextToken();
                int m = (int) in.nval;  //代表m的血量e

                for (int j = 0; j < n; j++) {
                    in.nextToken();
                    kill[j] = (int) in.nval;  //每个技能的伤害
                    in.nextToken();
                    blood[j] = (int) in.nval; //怪物血量小于等于blood[j]的时候该技能会造成双倍伤害
                }

                int ans = f(n,0,m);
                out.println(ans == Integer.MAX_VALUE ? -1 : ans);
            }
        }
        out.flush();
        br.close();
        out.close();

    }

    //n表示有几个技能
    //i表示当前使用第几个技能
    //r表示当前剩余的血量
    public static int f(int n, int i, int r){
        if(r <= 0){ //怪兽没血了，返回用了几个技能
            return i;
        }

        if(i == n){
            return Integer.MAX_VALUE;  //技能用完了，怪兽还有血，则技能释放顺序失败
        }

        int ans = Integer.MAX_VALUE;

        for(int j = i; j < n; j++){
            swap(i,j);
            int damage = r > blood[i] ? kill[i] : 2 * kill[i];  //本次技能释放的伤害
            ans = Math.min(ans, f(n, i+1, r - damage));
            swap(i,j);
        }
        return ans;
    }

    public static void swap(int i, int j){
        int temp1 = kill[i];
        kill[i] = kill[j];
        kill[j] = temp1;

        int temp2 = blood[i];
        blood[i] = blood[j];
        blood[j] = temp2;
    }
}
